/* 给你一个可装载重量为W的背包和N个物品，每个物品有重量和价值两个属性。
 * 其中第i个物品的重量为wt[i]，价值为val[i]
 * 现在让你用这个背包装物品，最多能装的价值是多少？
 */
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

class maxValue {
public:
    int maxValueInBag(int* weight, int* value, int n, int W) {
        // dp[w][i]: 对于前i个物品，在容量为w的背包中的最大价值
        int dp[W + 1][n + 1];
        for (int w = 0; w < W; w++)
            dp[w][0] = 0;
        for (int i = 0; i < n; i++)
            dp[0][i] = 0;

        for (int w = 1; w <= W; w++) {
            for (int i = 1; i <= n; i++) {
                if (w < weight[i - 1])
                    // 无法放入第i个物品
                    dp[w][i] = dp[w][i - 1];
                else
                    // 可以放入第i个物品，取是否放入得到的最大值
                    // 不放入dp[w][i] = dp[w][i - 1];
                    // 放入dp[w][i] = dp[w - weight[i - 1]][i - 1] + value[i - 1] (去掉第i个物品重量下背包对前i-1个物品的最大价值);
                    dp[w][i] = max(dp[w - weight[i - 1]][i - 1] + value[i - 1], dp[w][i - 1]);
            }
        }
        return dp[W][n];
    }
    int maxValueInBagN(int *weight, int *value, int n, int W) {
        int dp[W + 1];
        for (int w = 0; w < W; w++)
            dp[w] = 0;

        for (int w = 1; w <= W; w++) {
            // 必须逆序放, 否则可能重复放某个物体
            for (int i = n; i >= 1; i--) {
                if (w < weight[i - 1])
                    continue;
                dp[w] = max(dp[w - weight[i - 1]] + value[i - 1], dp[w]);
            }
        }
        return dp[W];
    }
};


// 分割等和子集
class Solution1 {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        for (int i = 0; i < n; i++)
            sum += nums[i];
        sum /= 2;

        int dpTable[sum][n];
        for (int i = 0; i < n; i++)
            dpTable[0][i] = true;
        for (int w = 1; w <= sum; w++)
            dpTable[w][0] = false;
        for (int w = 1; w <= sum; w++) {
            for (int i = 1; i < n; i++) {
                if (w < nums[i])
                    // 无法放入背包
                    dpTable[w][i] = dpTable[w][i - 1];
                else
                    dpTable[w][i] = dpTable[w - nums[i]][i - 1] | dpTable[w][i - 1];
            }
        }
        return dpTable[sum][n - 1];
    }
};

// 优化空间：
class Solution2 {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        for (int i = 0; i < n; i++)
            sum += nums[i];
    
        if (sum % 2 != 0)
            return false;
        sum /= 2;

        bool dpTable[sum + 1];
        memset(dpTable, 0, sizeof(dpTable));
        dpTable[0] = true;    
    
        for (int i = 0; i < n; i++)
            for (int w = sum; w >= 0; w--)
                if (w >= nums[i])
                    // 可以放入背包
                    dpTable[w] = dpTable[w] || dpTable[w - nums[i]];

        return dpTable[sum];
    }
};

// 完全背包--凑硬币
class coinsChange {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        int dp[amount + 1][n + 1];

        for (int i = 0; i <= amount; i++) 
            dp[i][0] = 0;
        for (int i = 0; i <= n; i++)
            dp[0][i] = 1;
        
        for (int i = 1; i <= amount; i++)
            for (int j = 1; j <= n; j++) {
                if (i >= coins[j - 1])
                    dp[i][j] = dp[i][j - 1] + dp[i - coins[j - 1]][j];
                else
                    dp[i][j] = dp[i][j - 1];
            }
        
        return dp[amount][n];
    }
};

// 优化
class coinsChange2 {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        int dp[amount + 1];
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        
        for (int i = 0; i < n; i++)
            for (int j = 1; j <= amount; j++) {
                if (j >= coins[i])
                    dp[j] = dp[j] + dp[j - coins[i]];
            }
        
        return dp[amount];
    }
};